package low;

import com.eclipsesource.json.JsonArray;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 733. 图像渲染
 */
public class NumWays {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for(int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static int[][] stringToInt2dArray(String input) {
        JsonArray jsonArray = JsonArray.readFrom(input);
        if (jsonArray.size() == 0) {
            return new int[0][0];
        }

        int[][] arr = new int[jsonArray.size()][];
        for (int i = 0; i < arr.length; i++) {
            JsonArray cols = jsonArray.get(i).asArray();
            arr[i] = stringToIntegerArray(cols.toString());
        }
        return arr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);
            line = in.readLine();
            int[][] relation = stringToInt2dArray(line);
            line = in.readLine();
            int k = Integer.parseInt(line);

            int ret = new SolutionBFS().numWays(n, relation, k);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }

    /**
     * bfs
     */
    static class SolutionBFS {
        public int numWays(int n, int[][] relation, int k) {
            int way = 0;
            Queue<Integer> queue = new LinkedBlockingQueue<>();
            queue.offer(0);
            int step = 0;
            while (!queue.isEmpty()&&step<k){
                step++;
                int size = queue.size();
                for (int i=0;i<size;i++){
                    int index = queue.poll();
                    for (int[] item:relation){
                        if (item[0]==index){
                            if (step==k&&item[1]==n-1){
                                way++;
                            }else {
                                queue.offer(item[1]);
                            }
                        }
                    }
                }
            }
            return way;
        }
    }

    /**
     * dfs
     */
    static class SolutionDFS {
        int way = 0;
        int k;
        int n;
        public int numWays(int n, int[][] relation, int k) {
            this.k = k;
            this.n = n;
            dfs(relation,0,0);
            return way;
        }

        private void dfs(int[][] relation,int index, int step) {
            if (step>k){
                return;
            }
            if (step==k&&index==n-1){
                way++;
                return;
            }
            for (int[] item:relation){
                if (index==item[0]){
                    dfs(relation,item[1],step+1);
                }
            }
        }


    }
}
